GRIM-Filter: Fast Seed Location Filtering in DNA Read Mapping Using Processing-in-Memory Technologies

摘要

Motivation: Seed location filtering is critical in DNA read mapping, aprocess where billions of DNA fragments (reads) sampled from a donor are mappedonto a reference genome to identify genomic variants of the donor.State-of-the-art read mappers 1) quickly generate possible mapping locationsfor seeds (i.e., smaller segments) within each read, 2) extract referencesequences at each of the mapping locations, and 3) check similarity betweeneach read and its associated reference sequences with acomputationally-expensive algorithm (i.e., sequence alignment) to determine theorigin of the read. A seed location filter comes into play before alignment,discarding seed locations that alignment would deem a poor match. The idealseed location filter would discard all poor match locations prior to alignmentsuch that there is no wasted computation on unnecessary alignments. Results: We propose a novel seed location filtering algorithm, GRIM-Filter,optimized to exploit 3D-stacked memory systems that integrate computationwithin a logic layer stacked under memory layers, to performprocessing-in-memory (PIM). GRIM-Filter quickly filters seed locations by 1)introducing a new representation of coarse-grained segments of the referencegenome, and 2) using massively-parallel in-memory operations to identify readpresence within each coarse-grained segment. Our evaluations show that for asequence alignment error tolerance of 0.05, GRIM-Filter 1) reduces the falsenegative rate of filtering by 5.59x--6.41x, and 2) provides an end-to-end readmapper speedup of 1.81x--3.65x, compared to a state-of-the-art read mapperemploying the best previous seed location filtering algorithm. Availability: The code is available online at:https://github.com/CMU-SAFARI/GRIM